package com.study.lu.链表;

public class 链表内指定区间反转 {
    /**
     * 描述
     * 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度
     * 示例1
     * {1,2,3,4,5},2,4
     * {1,4,3,2,5}
     */
    public static void main(String[] args) {

    }

    /**
     * @param head ListNode类
     * @param m    int整型
     * @param n    int整型
     * @return ListNode类
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        //1.走left-1步到left的前一个节点
        ListNode leftNode = dummyNode;
        for (int i = 0; i < m - 1; i++) {
            leftNode = leftNode.next;
        }

        //2.走roght-left+1步到right节点
        ListNode rightNode = leftNode;
        for (int i = 0; i <n-m+1; i++) {
            rightNode = rightNode.next;
        }

        // 3.截取出一个子链表
        ListNode leftNodeTemp = leftNode.next;
        ListNode cur = rightNode.next;

        //4.切断链接
        leftNode.next=null;
        rightNode.next=null;

        //5.反转局部链表
        reverseLinkedList(leftNodeTemp);

        //6.接回原来的链表
        leftNode.next = rightNode;
        leftNodeTemp.next = cur;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            //Cur_next 指向cur节点的下一个节点
            ListNode Cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = Cur_next ;
        }
    }
}
